package io.github.maojian.map;

import org.junit.Test;

import java.util.*;

/**
 * @Auther: jian.mao
 * @Date: 2022/4/25 13:14
 * @Description:
 */
public class Q398 {
    Map<Integer, List<Integer>> pos;
    Random random;

    public Q398() {
    }

    public Q398(int[] nums) {
        pos = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            pos.putIfAbsent(nums[i], new ArrayList<>());
            pos.get(nums[i]).add(i);
        }
    }

    public int pick(int target) {
        random = new Random();
        List<Integer> list = pos.get(target);
        return list.get(random.nextInt(list.size()));
    }


    static final int MAXIMUM_CAPACITY = 1 << 30;

    static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1, 2, 2, 3, 3, 3, 4, 4, 4, 4};
        Q398 q398 = new Q398(nums);
        System.out.println(q398.pick(4));

        System.out.println(q398.tableSizeFor(7));
    }
}
